package scenario;

import org.junit.Test;

import java.util.Arrays;

public class TrappingRainWater42 {

    @Test
    public void test() {
        trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
        trap(new int[]{4,2,0,3,2,5});
    }

    public int trap(int[] h) {
        // rightMax[i] = max(h[i+1], ....h[n])
        int[] rightMax = new int[h.length];
        rightMax[h.length-1] = 0;
        for (int i = h.length-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], h[i+1]);
        }

        int total = 0;
        int leftMax = 0;
        for (int i = 1; i < h.length-1; i++) {
            leftMax = Math.max(leftMax, h[i-1]);
            int water = Math.min(leftMax, rightMax[i]) - h[i];
            if (water > 0) {
                total += water;
            }
        }
        System.out.format("height: %s, total: %d\n", Arrays.toString(h), total);
        return total;
    }
}
